package com.test.daily.leetcode.y2022.m05.day0523.v04;

import java.util.ArrayList;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/23 上午 10:16
 * @version: 1.0
 */
public class Solution {
    public static class Node{
        int value;
        Node left;
        Node right;
        public Node(int value){
            this.value = value;
        }
    }
    public static int max1(Node root){
        if(root == null){
            return 0;
        }
        int ans = maxBT(root);
        if(ans != 0){
            return ans;
        }
        return Math.max(max1(root.left), max1(root.right));
    }
    public static int maxBT(Node root){
        ArrayList<Integer> list = new ArrayList<>();
        in(root,list);
        return sizeBST(list);
    }
    public static void in(Node root, ArrayList<Integer> list){
        if(root == null){
            return;
        }
        if(root.left != null){
            in(root.left, list);
        }
        list.add(root.value);
        if(root.right != null){
            in(root.right, list);
        }
    }
    public static int sizeBST(ArrayList<Integer> list){
        if(list == null || list.size() == 0){
            return 0;
        }
        for (int i = 0; i < list.size() - 1; i++) {
            if(list.get(i) > list.get(i+1)){
                return 0;
            }
        }
        return list.size();
    }
    public static class Info{
        public int allSize;
        public int maxSize;
        public int max;
        public int min;
        public Info(int allSize, int maxSize, int max, int min){
            this.allSize = allSize;
            this.maxSize = maxSize;
            this.max = max;
            this.min = min;
        }
    }
    public static int maxSizeBalanceTreeSize(Node root){
        if(root == null){
            return 0;
        }
        return process2(root).maxSize;
    }
    public static Info process2(Node root){
        if(root == null){
            return null;
        }
        Info leftInfo = process2(root.left);
        Info rightInfo = process2(root.right);
        int min = root.value;
        int max = root.value;
        int allSize = 1;
        if(leftInfo != null){
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
            allSize += leftInfo.allSize;
        }
        if(rightInfo != null){
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
            allSize += rightInfo.allSize;
        }
        int p1 = -1;
        if(rightInfo != null){
            p1 = rightInfo.maxSize;
        }
        int p2 = -1;
        if(leftInfo != null){
            p2 = leftInfo.maxSize;
        }
        int p3 = -1;
        boolean leftBalance = root.left == null? true: leftInfo.allSize == leftInfo.maxSize;
        boolean rightBalance = root.right == null?true:rightInfo.allSize == rightInfo.maxSize;
        if(leftBalance && rightBalance){
            boolean moreThanLeft = leftInfo == null? true: leftInfo.max < root.value;
            boolean lessThanRight = rightInfo == null ? true: root.value < leftInfo.min;
            if(moreThanLeft && lessThanRight){
                int leftSize = leftInfo == null ? 0: leftInfo.maxSize;
                int rightSize = rightInfo == null ? 0: rightInfo.maxSize;
                p3 = leftSize + rightSize + 1;
            }
        }
        return new Info(allSize,Math.max(p3, Math.max(p1, p2)), min, max);
    }
}
